package DataStructureAndAlgorithm.Acwing.DP.背包问题DP.分组背包DP;

import java.util.Scanner;
/*
* 完全背包问题：
*状态描述：dp[i][j]表示所有从前i个公司中选，总分配设备数量不超过j的方案
* 状态转移方程：dp[i][j]：Math.max(dp[i - 1][j],dp[i - 1][j - k] + num[i][k]);
*   当k从0开始时，可以直接写成：dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k] + num[i][k]);
*
*
* 计算具体方案的路径：
* 遍历所有组： i： 1 ~ n
*     每组遍历所有体积(设备台数)  j : v ~ 1
*         计算所有情况的盈利值（循环决策）k: 0 ~ j 每个组选的设备从0 ~ 最大限制
* 循环输出每组的编号
* */
class dp_1013 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[][] num = new int[N + 1][M + 1];
        int[][] dp = new int[N + 1][M + 1];
        //dp[i][j]：表示所有从前i个公司中选，分配的机器数不超过j的选法
        //依次枚举前i个物品
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                num[i][j] = in.nextInt();
            }
            //依次枚举体积
            for (int j = 0; j <= M; j++) {
                //依次枚举每种决策
                for (int k = 0; k <= j; k++) {
                    //注意，当k从0开始时，这里的转换方程，与完全背包问题的分析是一样的
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k] + num[i][k]);
                }
            }
        }
        System.out.println(dp[N][M]);
        //下面求方案路径，即逆推的过程
        //j为初始总体积
        int j = M;
        //逆着求路径
        for (int i = N; i > 0; i--) {
            //从最后一个值，往回找到当前状态是由前面哪个状态转移过来的，即可视为路径
            for (int k = 0; k <= j; k++) {
                //当前状态由前一个状态转移过来的条件
                if (dp[i][j] == dp[i - 1][j - k] + num[i][k]) {
                    System.out.println(i + " " + k);
                    //每次找到上一个状态之后，要把j置为上一个状态时候的总体积，再接着往下找
                    j = j - k;
                    break;
                }
            }
        }
    }
}
/*
总公司拥有M台 相同 的高效设备，准备分给下属的N个分公司。

各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。

问：如何分配这M台设备才能使国家得到的盈利最大？

求出最大盈利值。

分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。
输入格式

第一行有两个数，第一个数是分公司数N，第二个数是设备台数M；

接下来是一个N*M的矩阵，矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。
输出格式

第一行输出最大盈利值；

接下N行，每行有2个数，即分公司编号和该分公司获得设备台数。

答案不唯一，输出任意合法方案即可。
数据范围

1≤N≤10
,
1≤M≤15

输入样例：

3 3
30 40 50
20 30 50
20 25 30

输出样例：

70
1 1
2 1
3 1

 */